package com.gxc.graph;

import java.util.HashMap;

/**
 * 自定义小跟堆
 */
public class NodeHeap {

    private Node[] nodes;
    private HashMap<Node, Integer> heapIndexMap;
    private HashMap<Node, Integer> distanceMap;
    private int size;

    public NodeHeap(int size1) {
        size = 0;
        nodes = new Node[size1];
        heapIndexMap = new HashMap<>();
        distanceMap = new HashMap<>();
    }

    private void heapify(int index, int heapszie) {
        //左子节点
        int left = 2*index+1;
        while (left<heapszie) {
            //左右子节点比较大小
            int smlllest = left+1<heapszie && heapIndexMap.get(nodes[left+1])<heapIndexMap.get(nodes[left])?left+1:left;
            //左右子节点大数和父节点比较
            smlllest = heapIndexMap.get(nodes[smlllest])<heapIndexMap.get(nodes[index])?smlllest:index;

            if(smlllest == index) break;

            swap(index, smlllest);
            index = smlllest;
            left = 2*index+1;
        }
    }

    private void heapInsert(Node node, int index) {
        while (heapIndexMap.get(nodes[index])>heapIndexMap.get(nodes[(index-1)/2])) {
            swap(index, (index-1)/2);
            index = (index-1)/2;
        }
    }

    public void addOrUpdateOrIgnore(Node node, int distance) {
        if (inHeap(node)) {
            distanceMap.put(node, Math.min(distanceMap.get(node), distance));
            heapInsert(node, heapIndexMap.get(node));
        } else if (!isEntered(node)) {
            nodes[size] = node;
            heapIndexMap.put(node, size);
            distanceMap.put(node, distance);
            heapInsert(node, size++);
        }
    }

    public boolean isEmpty() {
        return size==0;
    }

    /**
     * node是否进入过堆
     * @param node
     * @return
     */
    private boolean isEntered(Node node) {
        return heapIndexMap.containsKey(node);
    }

    /**
     * node是否在堆上
     * @param node
     * @return
     */
    private boolean inHeap(Node node) {
        return isEntered(node) && heapIndexMap.get(node)!=-1;
    }

    private void swap(int index1, int index2) {
        heapIndexMap.put(nodes[index1], index2);
        heapIndexMap.put(nodes[index2], index1);

        Node temp = nodes[index1];
        nodes[index1] = nodes[index2];
        nodes[index2] = temp;
    }

    public NodeRecord pop() {
        NodeRecord record = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
        swap(0, size-1);
        heapIndexMap.put(nodes[size-1], -1);
        distanceMap.remove(nodes[size-1]);
        nodes[size-1] = null;
        heapify(0, --size);
        return record;
    }
}
